package 数据结构专栏.D_数组;

/**
 * https://zhuanlan.zhihu.com/p/99159225
 * 时间复杂度： [公式] 。每个元素最多被访问一次，共有 [公式] 个元素。
 * 空间复杂度： [公式] 。只是用了两个指针。
 * <p>
 * 输入: numbers = [2, 7, 11, 15], target = 9
 * 输出: [1,2]
 * 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
 */
public class 两数之和 {


    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        // 双指针，左右指针往中间靠拢
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) {
                res[0] = l + 1;
                res[1] = r + 1;
                return res;
            } else if (sum > target) {
                r--;
            } else {
                l++;
            }
        }

        // 暴力最简单
        // for (int i = 0; i < numbers.length; i++) {
        //     for (int j = i + 1; j < numbers.length; j++) {
        //         if (numbers[i] + numbers[j] == target) {
        //             res[0] = i + 1;
        //             res[1] = j + 1;
        //             return res;
        //         }
        //     }
        // }
        return res;
    }
}



//Solution链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/solution/liang-shu-zhi-he-ii-shu-ru-you-xu-shu-zu-by-leet-2/
